package leetcode.code0037;

import java.util.Stack;

public class Solution extends Solution37 {

	private int[] row = new int[10];
	private int[] col = new int[10];
	private int[] area = new int[10];
	Stack<int[]> q = new Stack<>();

	@Override
	public void solveSudoku(char[][] board) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				char c = board[i][j];
				if (c == '.') {
					q.add(new int[] { i, j });
					continue;
				}
				int u = c - '0';
				this.takeOver(i, j, u);
			}
		}
		if (this.fillBlanks(board))
			return;
	}

	public boolean fillBlanks(char[][] board) {
		int[] pos = q.pop();
		int avl = this.avaliable(pos[0], pos[1]);
		if (avl > 9) {
			q.add(pos);
			return false;// 这个位置没有可用的数字,这条线都错了,返回
		}
		if (q.isEmpty()) {
			board[pos[0]][pos[1]] = (char) ('0' + avl);
			return true;// 这个位置可用,并且是最后一个数字,找对了,返回
		}
		int avlList = this.avaliableList(pos[0], pos[1]);
		for (int i = 1; i < 10; i++) {
			if (((avlList >> i) & 1) == 1) {
				board[pos[0]][pos[1]] = (char) ('0' + i);
				this.takeOver(pos[0], pos[1], i);
				boolean fill = this.fillBlanks(board);
				if (fill)
					return true;
				this.untakeOver(pos[0], pos[1], i);
			}
		}
		q.add(pos);
		return false;
	}

	private void untakeOver(int i, int j, int k) {
		int zero = (-1 << (k + 1)) | ((1 << k) - 1);
		row[i] &= zero;
		col[j] &= zero;
		area[this.areaIndex(i, j)] &= zero;
	}

	private void takeOver(int i, int j, int k) {
		row[i] |= (1 << k);
		col[j] |= (1 << k);
		area[this.areaIndex(i, j)] |= (1 << k);
	}

	private int areaIndex(int i, int j) {
		return i / 3 * 3 + j / 3;
	}

	private int avaliable(int i, int j) {
		return this.avaliable(row[i], col[j], area[this.areaIndex(i, j)]);
	}

	public int avaliable(int row, int col, int area) {
		int num = (row | col | area) >> 1;
		int ans = 1;
		while ((num & 1) == 1) {
			ans++;
			num >>= 1;
		}
		return ans;
	}

	private int avaliableList(int i, int j) {
		return this.avaliableList(row[i], col[j], area[this.areaIndex(i, j)]);
	}

	public int avaliableList(int row, int col, int area) {
		int num = row | col | area;
		int ans = 0;
		for (int i = 0; i < 9; i++) {
			num >>= 1;
			if ((num & 1) == 0) {
				ans |= 1 << (i + 1);
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		int ans = 0;
		for (int i = 1; i < 10; i++) {
			int n = 1 << i;
			String temp = Integer.toBinaryString(1 << i);
			System.out.println(temp);
			ans |= n;
		}

		int temp = so.avaliableList(1 << 3, 1 << 5, 1 << 7);
		System.out.println(temp);
		System.out.println(Integer.toBinaryString(temp));

		temp = so.avaliable((1 << 3) | (1 << 1), 1 << 5, 1 << 7);
		System.out.println(temp);
		System.out.println(Integer.toBinaryString(temp));
		System.out.println(Integer.toBinaryString(-1));

		int num = 5;
		int zero = (-1 << (num + 1)) | ((1 << num) - 1);
		int n = (1 << 3) | 1 << 5 | 1 << 7;
		System.out.println(Integer.toBinaryString(n & zero));
		System.out.println(Integer.toBinaryString(zero));
		System.out.println(Character.forDigit(9, 10));
		System.out.println(Character.forDigit(4, 10));
		System.out.println(Character.forDigit(3, 10));
		System.out.println(Integer.toBinaryString(1006));
	}

}
